import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/7 14:27
 * @description 前缀和 O(n^2)
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        int[] arr = {1, 4, 2, 5, 3};
        solution.sumOddLengthSubarrays(arr);
    }
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int[] prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + arr[i];
        }
        int sum = 0;
        for (int start = 0; start < n ; start++) {
            for (int length = 1; start + length <=n ; length+= 2) {
                int end = start + length - 1;
                sum += prefixSums[end + 1] - prefixSums[start];
            }
        }
        return sum;
    }
}
